import java.util.*;

/**
 * Creat with IntelliJ IDEA
 * Description:
 * User:WZW
 * Date:2022-09-29
 * Time:9:19
 */

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
    this.val = val;
    }
}

class Solution03 {

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 二叉树前序遍历
     * @param root TreeNode类
     * @return int整型一维数组
     */

    public ArrayList<Integer> preorderTraversal (TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if (root == null) return list;
        preTraversal(list, root);
        return list;
    }

    // 使用栈
    public ArrayList<Integer> preorderTraversal2 (TreeNode root) {
        ArrayList<Integer> ret = new ArrayList<>();
        if (root == null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            ret.add(cur.val);
            if (cur.right != null)
                stack.push(cur.right);
            if (cur.left != null)
                stack.push(cur.left);
        }
        return ret;
    }

    public void preTraversal (ArrayList<Integer> list, TreeNode root) {
        if (root == null) return;
        list.add(root.val);
        if (root.left != null)
            preTraversal(list, root.left);
        if (root.right != null)
            preTraversal(list, root.right);
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 二叉树中序遍历
     * @param root TreeNode类
     * @return int整型一维数组
     */
    public ArrayList<Integer> inorderTraversal (TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) return list;
        inTraversal(list, root);
        return list;
    }

    private void inTraversal(ArrayList list, TreeNode root) {
        if (root == null) return;
        if (root.left != null) inTraversal(list, root.left);
        list.add(root.val);
        if (root.right != null) inTraversal(list, root.right);
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 后序遍历
     * @param root TreeNode类
     * @return int整型一维数组
     */
    public ArrayList<Integer> postorderTraversal (TreeNode root) {
        ArrayList list = new ArrayList();
        if (root == null) return list;
        postTraversal(list, root);
        return list;
    }

    private void postTraversal(ArrayList list, TreeNode root) {
        if (root == null) return;
        if (root.left != null) postTraversal(list, root.left);
        if (root.right != null) postTraversal(list, root.right);
        list.add(root.val);
    }

    /**
     * 二叉树的层序遍历
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> list = new ArrayList();
        if (root == null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> l = new ArrayList();
            while (size > 0) {
                TreeNode cur = queue.poll();
                l.add(cur.val);
                if (cur.left != null)
                    queue.offer(cur.left);
                if (cur.right != null)
                    queue.offer(cur.right);
                size--;
            }
            list.add(l);
        }
        return list;
    }


    /**
     * 按之字形顺序打印二叉树
     * @param root
     * @return
     */
    public ArrayList<ArrayList<Integer>> Print1(TreeNode root) {
        ArrayList<ArrayList<Integer>> list = new ArrayList();
        if (root == null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> l = new ArrayList();
            while (size > 0) {
                TreeNode cur = queue.poll();
                l.add(cur.val);
                if (cur.left != null)
                    queue.offer(cur.left);
                if (cur.right != null)
                    queue.offer(cur.right);
                size--;
            }
            if (i % 2 == 1)
                Collections.reverse(l);
            list.add(l);
            i++;
        }
        return list;
    }

    /**
     *  法二：使用两个栈
     * @param root
     * @return
     */
    public ArrayList<ArrayList<Integer>> Print(TreeNode root) {
        ArrayList<ArrayList<Integer>> list = new ArrayList();
        if (root == null) return list;
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(root);
        int i = 0;
        int size = 0;
        while (!s1.isEmpty() || !s2.isEmpty()) {
            // 这里有变化
            if (i % 2 == 0) {
                size = s1.size();
            } else {
                size = s2.size();
            }
            ArrayList<Integer> l = new ArrayList();
            while (size > 0) {
                if (i % 2 == 0) {
                    TreeNode cur = s1.pop();
                    l.add(cur.val);
                    if (cur.left != null)
                        s2.push(cur.left);
                    if (cur.right != null)
                        s2.push(cur.right);
                    size--;
                } else {
                    TreeNode cur = s2.pop();
                    l.add(cur.val);
                    if (cur.right != null)
                        s1.push(cur.right);
                    if (cur.left != null)
                        s1.push(cur.left);
                    size--;
                }
            }
            list.add(l);
            i++;
        }
        return list;
    }

    /**
     * 二叉树的最大深度：层序遍历，，记录深度
     * @param root TreeNode类
     * @return int整型
     */
    public int maxDepth1 (TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int height = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                TreeNode cur = queue.poll();
                if (cur.left != null)
                    queue.offer(cur.left);
                if (cur.right != null)
                    queue.offer(cur.right);
                size--;
            }
            height++;
        }
        return height;
    }

    /**
     * 二叉树的最大深度法二：递归
     * 二叉树的深度 = max(左子树的深度, 右子树的深度) + 1
     * @param root TreeNode类
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        if (root == null) return 0;
        int l = maxDepth(root.left);
        int r = maxDepth(root.right);
        return 1 + (l > r ? l : r);
    }

    /**
     * 二叉树中和为某一值的路径
     * @param root TreeNode类
     * @param sum int整型
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        return PathSum(root, sum, 0) == 0;
    }

    private int PathSum(TreeNode root, int sum, int val) {
        if (root == null) return -1;
        val += root.val;
        if (val == sum && root.left == null && root.right == null)
            return 0;
        int l = PathSum(root.left, sum, val);
        if (l == 0) return 0;
        return PathSum(root.right, sum, val);
    }

    /**
     * 二叉搜索树与双向链表
     * @param pRootOfTree
     * @return
     */
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null || pRootOfTree.left == null && pRootOfTree.right == null)
            return pRootOfTree;
        TreeNode ret = null;
        if (pRootOfTree.left != null) {
            TreeNode l = Convert(pRootOfTree.left);
            TreeNode cur = l;
            ret = l;
            while (cur.right != null) {
                cur = cur.right;
            }
            cur.right = pRootOfTree;
            pRootOfTree.left = cur;
        }
        if (pRootOfTree.right != null) {
            TreeNode r = Convert(pRootOfTree.right);
            TreeNode cur = r;
            while (cur.right != null) {
                cur = cur.right;
            }
            pRootOfTree.right = r;
            r.left = pRootOfTree;
            if (ret == null)
                ret = pRootOfTree;
        }
        return ret;
    }

    /**
     * 对称二叉树
     * @param pRoot
     * @return
     */
    boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot == null) return true;
        return isSym(pRoot.left, pRoot.right);
    }

    private boolean isSym(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null || left.val != right.val) return false;
        if (isSym(left.left, right.right) == false) return false;
        return isSym(left.right, right.left);
    }


    /**
     * 合并二叉树
     * @param t1 TreeNode类
     * @param t2 TreeNode类
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        t1.val += t2.val;
        if (t1.left == null && t2.left != null) {
            t1.left = new TreeNode(0);
        }
        mergeTrees(t1.left, t2.left);
        if (t1.right == null && t2.right != null) {
            t1.right = new TreeNode(0);
        }
        mergeTrees(t1.right, t2.right);
        return t1;
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 二叉树的镜像
     * @param pRoot TreeNode类
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        if (pRoot == null) return pRoot;
        Mirror(pRoot.left);
        Mirror(pRoot.right);
        TreeNode tmp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = tmp;
        return pRoot;
    }


    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 判断是否是二叉搜索树
     * @param root TreeNode类
     * @return bool布尔型
     */
    public TreeNode parent = null;
    public boolean isValidBST (TreeNode root) {
        if (root == null) return true;
        if (root.left != null && root.left.val >= root.val) return false;
        if (root.right != null && root.right.val <= root.val) return false;
        if (parent != null) {
            if (root == parent.left && root.right != null && root.right.val >= parent.val) return false;
            if (root == parent.right && root.left != null && root.left.val <= parent.val) return false;
        }
        parent = root;
        return isValidBST(root.left) && isValidBST(root.right);
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 判断是不是完全二叉树
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean flg = false;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                size--;
                TreeNode cur = queue.poll();
                if (cur == null) {
                    flg = true;
                    continue;
                }
                if (flg)
                    return false;
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
        }
        return true;
    }

    // 判断是否平衡二叉树
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) return true;
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode root) {
        if (root == null) return 0;
        int l = getHeight(root.left);
        int r = getHeight(root.right);
        if (l == -1 || r == -1) return -1;
        if (Math.abs(l - r) > 1)
            return -1;
        return Math.max(l, r) + 1;
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 二叉搜索树的最近公共祖先
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    public int lowestCommonAncestor0 (TreeNode root, int p, int q) {
        if (root == null) return -1;
        if (root.val == p || root.val == q) return root.val;
        if ((p < root.val && q > root.val) || (p > root.val && q < root.val)) return root.val;
        if (p < root.val && q < root.val) return lowestCommonAncestor(root.left, p, q);
        return lowestCommonAncestor(root.right, p, q);
    }

    /**
     * 二叉树的最近公共祖先
     * @param root TreeNode类 保证非空
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    //有问题
    public int lowestCommonAncestor1 (TreeNode root, int o1, int o2) {
        if (root == null) return -1;
        Stack s1 = new Stack();
        Stack s2 = new Stack();
        getPath(root, o1, s1);
        getPath(root, o2, s2);
        if (s1.size() > s2.size()) {
            int step = s1.size() - s2.size();
            while (step-- > 0) {
                s1.pop();
            }
            while (!s1.isEmpty() && ! s2.isEmpty() && s1.peek() != s2.peek()) {
                s1.pop();
                s2.pop();
            }
            return (int) s1.pop();
        } else {
            int step = s2.size() - s1.size();
            while (step-- > 0) {
                s2.pop();
            }
            while (!s1.isEmpty() && ! s2.isEmpty() && s1.peek() != s2.peek()) {
                s1.pop();
                s2.pop();
            }
            return (int) s1.pop();
        }
    }

    public boolean getPath(TreeNode root, int val, Stack<Integer> stack) {
        if (root == null) return false;
        stack.push(root.val);
        if (root.val == val) {
            return true;
        }
        if (getPath(root.left, val, stack)) {
            return true;
        }
        if (getPath(root.right, val, stack)) {
            return true;
        }
        stack.pop();
        return false;
    }

    //递归法
    public int lowestCommonAncestor2 (TreeNode root, int o1, int o2) {
        if (root == null) {
            return -1;//没找到
        }
        if (root.val == o1 || root.val == o2) {
            return root.val;
        }
        int left = lowestCommonAncestor(root.left, o1, o2);
        int right = lowestCommonAncestor(root.right, o1, o2);
        if (left == -1) {
            return right;
        }
        if (right == -1) {
            return left;
        }
        return root.val;
    }

    // 官方解法
    public boolean flag = false;
    public void dfs (TreeNode root, ArrayList<Integer> path, int o) {
        if (flag || root == null) {
            return;
        }
        path.add(root.val);
        if (root.val == o) {
            flag = true;
            return;
        }
        dfs(root.left, path, o);
        dfs(root.right, path, o);
        if (flag)
            return;
        //回溯
        path.remove(path.size()-1);
    }
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        ArrayList<Integer> p1 = new ArrayList<>();
        ArrayList<Integer> p2 = new ArrayList<>();
        dfs(root,p1,o1);
        flag = false;
        dfs(root,p2,o2);
        int res = 0;
        for (int i = 0; i < p1.size() && i < p2.size(); i++) {
            int a = p1.get(i);
            int b = p2.get(i);
            if (a == b) {
                res = a;
            } else {
                break;
            }
        }
        return res;
    }
}

public class Test03 {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(3);
        TreeNode node2 = new TreeNode(5);
        TreeNode node3 = new TreeNode(1);
        TreeNode node4 = new TreeNode(6);
        TreeNode node5 = new TreeNode(2);
        TreeNode node6 = new TreeNode(0);
        TreeNode node7 = new TreeNode(8);
        TreeNode node8 = new TreeNode(7);
        TreeNode node9 = new TreeNode(4);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node5.left = node8;
        node5.right = node9;
        Solution03 s = new Solution03();
        System.out.println(s.lowestCommonAncestor(node1, 2, 7));
    }
}
